#include<cstdio>
#include<iostream>
using namespace std;
long long s1,v1,s2,v2,N,x,y,ans;
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
	return a/gcd(a,b)*b;
}
long long max(long long a,long long b)
{
	if(a>b)return a;
	return b;
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++)
	{
		ans=0;
		cin>>N>>s1>>v1>>s2>>v2;		
		long long LCM=lcm(s1,s2);
		if(v1*s2<v2*s1||v1*s2==v2*s1&&s1>s2) // 1的价值小于2的价值
		{
			long long t=v1;v1=v2;v2=t;
			t=s1;s1=s2;s2=t;
		}
		long long vn=N%LCM+LCM;
		if(N>2*LCM)
		{			
			int t=(N-vn)/s1;
			ans+=t*v1;
		}
		else vn=N;
	    long long maxn=0;
		if(s1>s2)
			for(int i=0;i<=vn/s1;i++)
			{
			long long j=(vn-i*s1)/s2;
			maxn=max(maxn,i*v1+j*v2);
			}
		else
			for(int j=0;j<=vn/s2;j++)
			{
				long long i=(vn-j*s2)/s1;
				maxn=max(maxn,i*v1+j*v2);
			}

		cout<<"Case #"<<cas<<": "<<ans+maxn<<endl;
	}
	return 0;
}

